Network coding and Quality of Service (QoS) provisioning are well-known in the art. With respect to QoS provisioning, traditional schemes can be seen as a complement rather than an alternative to technologies described herein. Traditional schemes either treat the problem at the routing layer to find better paths (e.g., low delay, high bandwidth, minimum energy, etc.) or at the scheduler level to provide service differentiation across packets of different flows. For instance in H. Zhang, “Service disciplines for guaranteed performance service in packet-switching networks,” in the Proceedings of the IEEE, vol. 83, no. 10, October 1995 and R. Guerin and V. Peris, “Quality-of-Service in Packet Networks: Basic Mechanisms and Directions,” invited Paper, Computer Networks, Vol. 31, No. 3, February 1999, pp. 169-179, the authors present a survey of various service disciplines to be employed at a scheduler for guaranteed performance locally and end-to-end in packet-switching networks. These studies provide per-link guarantees or service differentiation for simple copy-and-forward based routing strategies. One can also provide differentiation at the Medium Access Control (MAC) layer. For example, in one well-known scheme, traffic is separated at the MAC layer into different (actual) queues, each with different probabilistic advantages to gaining access to the medium. One can further provide service differentiation at the physical layer, using different channel codes for different traffic classes.
Network coding has been discussed as a method for attaining the maximum jointly attainable throughput in a multicast session. FIG. 1A shows a sample network topology graph with one sender (S1), two receivers (R1 and R2) and four routers (labeled 1 to 4). Each vertex of the graph corresponds to a unique node in the network and each edge between a pair of vertices corresponds to the network interface/link between those vertices. In FIG. 1A, each edge can carry one symbol per unit time. A symbol for purposes herein can be a bit, a block of bits, a packet, etc. The terms “symbol” and “packet” are also used interchangeably herein. The best routing strategy that only copies an incoming symbol to an outgoing interface can deliver at best 1.5 symbols per receiver per unit time. This strategy is shown in FIG. 1A. The main limiting factor for the pure routing strategy, which only relies on a simple copy-and-forward mechanism, is at a bottleneck node (i.e., node 3). At node 3, the incoming interfaces have more bandwidth than the outgoing interfaces and decisions must be made as to which (proper) subset of the incoming symbols must be forwarded. For instance, in FIG. 1A, node 3 is a bottleneck node because it has two incoming interfaces with a total bandwidth of 2 symbols per unit time, and one outgoing interface with a total bandwidth of 1 symbol per unit time. Hence, when node 3 receives the two symbols “a” and “b” on each interface per unit time, it must either forward “a” or “b” on the outgoing interface, or some subset such as half of each portion of information. By allowing, however, each node (e.g., router) to send jointly encoded versions of sets of symbols (or packets) arriving at the incoming interfaces in each use of any outgoing interface, in general, coding strategies can be designed that outperform routing.
For the network shown in FIG. 1A, an example of such a coding strategy (referred to herein as “network coding”) is depicted in FIG. 1B. Instead of just copying an incoming symbol, node 3 performs a bit-wise modulo-2 addition (i.e., XOR two symbols) and sends (a+b) over the link between nodes 3 and 4. As a result of this operation, R1 receives a and (a+b) on two incoming interfaces, and can thus compute b by bitwise XORing a and (a+b). Similarly, R2 receives b and (a+b), and can also deduce a. As a result, network coding achieves on this network a multicast rate of 2 symbols per receiver per unit time, a 33.3% improvement over the 1.5 symbols per receiver per unit time attained by the routing-only strategy.
Network coding was originally proposed as a method for maximizing throughput in a multicast setting, i.e., for maximizing the minimum flow between any sender-receiver pair. It has been shown that encoding information at the interior nodes of the network achieves the multicast capacity (i.e., the minimum value of capacity over all cuts on the corresponding topology graph between the sender and any of the receivers) while simple routing (i.e., forwarding of the information), in general, does not. A cut between a source and a destination refers to a division of the network nodes into two sets, whereby the source is in one set and the destination is in the other. A cut is often illustrated by a line dividing the network (in a 2-dimensional space) into two half-planes, see T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd Edition, MIT Press and McGraw-Hill, pp. 643-700, 2001. The capacity of a cut is the sum of the capacities of all the edges crossing the cut and originating from the set containing the source and ending in nodes in the set containing the destination. The capacity of a cut also equals the sum of the transmission rates over all links crossing the cut, and transferring data from the set including the source to the set including the set including the destination. The cut with the minimum capacity is referred to herein as the “min cut” of the graph. The minimum cut equals the maximum flow through the entire graph (a fact known as the max-flow min-cut theorem), see T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd Edition, MIT Press and McGraw-Hill, pp. 643-700, 2001.
It is also well-known that linear encoding (i.e., linear combinations of incoming packets performed at the interior nodes) is sufficient to achieve the capacity of multicast networks. Furthermore, there exists polynomial-time algorithms to construct such multicast capacity achieving network codes in a deterministic fashion for a given fixed network topology. There also exists an algorithm for constructing network codes to recover from non-ergodic network failures (e.g., removal of a connection between two interior nodes) without requiring adaptation of the network code to the link failure pattern so long as the multicast capacity remains achievable under the given failure. For example, see R. Koetter and M. Medard, “An algebraic approach to network coding”, IEEE/ACM Transactions on Networking, Vol. 11, No. 5, pp. 782-795, October 2003. This requires knowledge of the family of failure patterns under which the network graph can still sustain the same multicast capacity. Hence, the existence of a network code design without knowing a priori exactly which failure will occur, but with the knowledge that any, but only one, failure in the family of failure patterns can occur at a given period of time.
The drawbacks of such approaches are that the network topology has to be available, i.e., the connections between the network nodes as well as their individual rates have to be known in order to derive the encoding and decoding operations at every node. Therefore, encoding and decoding algorithms are built for a given topology. The network codes that are generated by these code-construction algorithms usually change when the topology changes. There is an exception involving a multicast setup with link failures where robust multicast can be achieved with a static network code. The multicast results require that, as the network changes, the minimum cut capacity remains at least as large as the throughput of the designed static code. Alternatively, these techniques allow the use of a static code for multicasting at the minimum (over time) cut capacity, which may be considerably lower than the throughput achievable by network coding over the entire set of time-varying networks. Approaches to network coding in the prior art also assume that the networks are delay-free and acyclic, which, in general, is not the case for real networks. Furthermore, they do not consider different QoS classes.
A distributed scheme has been proposed that is robust to random packet losses, delays, cycles, as well as to any changes in the network topology (or capacity) due to nodes joining, leaving the network, node or link failures, congestion, etc. In this scheme, random network coding is used whereby the coefficients of the linear combination of incoming packets at every node are chosen randomly within a field of size 2. A value of m=8 (i.e., a field of size 256) has been shown to usually be large enough to recover the original source packets at any receiver with high probability. This scheme is distributed in the sense that it does not require any coordination between the sender and the receivers. Receivers can decode without knowing the network topology, the local encoding functions, or the links that have failed. This decentralization of network coding is achieved by including the vector of random coefficients within each encoded packet, at the expense of bandwidth (i.e., small overhead associated with the transmission of this extra information). A PET (Priority Encoding Transmission)-inspired erasure protection scheme at the source allows for providing different levels of protection to different layers of information. Also, in this scheme, a receiver can recover the symbols (in the given Galois field) in the most important layer by receiving only one encoded packet. Symbols in the second most important layer can be recovered if the receiver receives at least two linearly independent encoded packets, symbols in the third most important layer can be recovered if the receiver receives at least three linearly independent encoded packets, and so on. The proposed PET scheme is efficient, in the sense that it incurs the minimum required increase in rate in achieving this goal. However, this minimal increase in rate is still quite significant due to the stringent requirements/goals imposed on the scheme (e.g., that the top priority layer can be recovered from any single received packet, the top two priority layers can be recovered from any two received packets, etc.).
There are drawbacks associated with random distributed network coding, however. Firstly, each encoded packet has some overhead (e.g., random code coefficients) that has to be communicated to the receiver. This overhead may be significant for small-sized packets (e.g., in typical voice communications). Secondly, some encoded packets may not increase the rank of the decoding matrix, i.e., they may not be classified as “innovative” in providing additional independent information at the receiving nodes of these packets. These non-innovative packets typically waste bandwidth. As a result, the average time it takes to decode an original source packet in general increases. Transmission of non-innovative packets can be avoided by monitoring the network, i.e., each node arranges with its neighbors to transmit innovative packets only by sharing with them the innovative packets it has received so far. However, such additional monitoring uses extra network resources that could be used for other purposes. Random codes also have the processing overhead due to the use of a random number generator at each packet generation, decoding overhead due to the expensive Gaussian Elimination method they use, and decoding delay due to the fact that rank information of random matrices does not necessarily correspond to an instantaneous recovery rate and one may have to wait until the matrix builds enough rank information to decode partial blocks. The methods that guarantee partial recovery in proportion to the rank information require extra coding which can substantially increase the overhead.
A robust network code does not necessarily have to be random. For example, in one forwarding architecture for wireless mesh networks (COPE), coding opportunities are detected and exploited to forward multiple packets in a single transmission. Each node uses simple XOR operations to encode specific received packets; the packets to encode together are selected such that the node neighbors will be able to decode the coded packets (the method is called “opportunistic” coding). Therefore the bandwidth is used carefully to improve throughput. However, there are some drawbacks associated with this scheme as well. First, a node has to know what packets its neighbors have in order to send them useful (or innovative) packets. A node learns about its neighbors' state through “reception reports” that each node broadcasts in the network to let its neighbors know about which packets it has stored. These broadcast transmissions utilize bandwidth. Second, although the broadcast medium is exploited to let every node “hear” packets from other nodes for free (“opportunistic” listening), this can have security implications in the case that packets are not encrypted.